package cn.edu.anan.algorithm.sort;

import java.util.Arrays;

/**
 * 冒泡排序算法：
 *      1.时间复杂度：
 *          O(n^2)
 *      2.空间复杂度：
 *          O(1)是原地排序算法
 *      3.算法稳定性：
 *          是稳定排序算法
 */
public class BubbleSort {

    /**
     * 冒泡排序：优化实现版本
     * @param array：待排序数组
     * @param n：待排序数组大小
     */
    public static void sort_2(Integer [] array,int n){
        // 如果排序数组规模小于等于1，直接返回
        if(n <= 1){
            return;
        }

        // 优化标识
        // 如果某一次冒泡过程中，没有发生数据交换
        // 则说明已经排好了序，不需要在继续冒泡
        boolean flag = false;

        // n个元素，n次冒泡
        for(int i = 0; i < n; i++){

            // 重置是否发生交换标识
            flag = false;

            // 每一次冒泡中，比较交换相邻元素
            for(int j = 0; j < n-i-1; j++){
                if(array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;

                    // 发生了数据交换
                    flag = true;
                }
            }

            // 一次冒泡结束,检查是否发生了数据交换
            // 如果没有发生数据交换，说明序列已经有序，不需要再继续冒泡了
            System.out.println("第【" + (i+1) + "】次冒泡.");
            if( !flag){
                break;
            }

        }

    }

    /**
     * 冒泡排序：普通实现版本
     * @param array：待排序数组
     * @param n：待排序数组大小
     */
    public static void sort_1(Integer [] array,int n){
        // 如果排序数组规模小于等于1，直接返回
        if(n <= 1){
            return;
        }

        // 有n个元素，进行n次冒泡
        for(int i = 0; i < n; i++){

            // 每一次冒泡，比较交换相邻两个元素
            for(int j = 0; j < n-i-1; j++){
                if(array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }

    }
}
